import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 224. Basic Calculator 基本计算器
 * https://leetcode.com/problems/basic-calculator/
 */
class BasicCalculator {
    /**
     * 方法：计算包含加减法和括号的字符串表达式
     * 
     * Args:
     *   s: 字符串表达式，包含数字、'+'、'-'和括号
     * 
     * Returns:
     *   计算结果的整数值
     * 
     * Time: O(n) 其中n是字符串长度，需要遍历整个字符串
     * Space: O(n) 最坏情况下栈的深度与字符串长度成正比
     */
    public int calculate(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        int res = 0, num = 0, sign = 1;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+') {
                res += sign * num;
                num = 0;
                sign = 1;
            } else if (c == '-') {
                res += sign * num;
                num = 0;
                sign = -1;
            } else if (c == '(') {
                stack.push(res);
                stack.push(sign);
                res = 0;
                sign = 1;
            } else if (c == ')') {
                res += sign * num;
                res *= stack.pop();
                res += stack.pop();
                num = 0;
            }
        }
        return res + sign * num;
    }

    /**
     * 方法：使用栈来计算包含加减法和括号的字符串表达式，忽略空格
     * 
     * Args:
     *   s: String - 字符串表达式，包含数字、'+'、'-'、括号和空格
     * 
     * Returns:
     *   int - 计算结果的整数值
     * 
     * Time: O(n) - 其中n是字符串长度，需要遍历整个字符串
     * Space: O(n) - 最坏情况下栈的深度与字符串长度成正比
     */
    public int calculate1(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        int res = 0, num = 0, sign = 1;
        
        for (char c : s.toCharArray()) {
            switch (c) {
                case ' ' -> {}  // 忽略空格
                case '+' -> { res += sign * num; num = 0; sign = 1; }
                case '-' -> { res += sign * num; num = 0; sign = -1; }
                case '(' -> { stack.push(res); stack.push(sign); res = 0; sign = 1; }
                case ')' -> { res += sign * num; res *= stack.pop(); res += stack.pop(); num = 0; }
                default  -> { if (Character.isDigit(c)) num = num * 10 + (c - '0'); }
            }
        }
        return res + sign * num;
    }
}